Digital signature technique is available to guarantee the integrity of an electronic document. In the field of the applications of electronic documents, there is an increasing need for partially extracting a signed electronic document. Since the extraction of the electronic document means altering the electronic document in the application of digital signature, the integrity of the document cannot be guaranteed. To overcome this problem, partial extraction techniques of digital signature such as sanitization signature or deletion signature has been developed. These techniques guarantee the integrity of a portion of the electronic document even if the portion is extracted.
Extraction signature is defined here. In a standard digital signature, a two-party model is used. The two-party model includes a signer who signs and a verifier who verifies the digital signature. In contrast, in the extraction signature, a three-party model is used. The three-party model includes a signer who signs a electronic document, an extractor who extracts a portion of the electronic document signed by the signer, and a verifier who verifies the extracted document as illustrated in FIG. 11. The signer signs the electronic document in any available method. The extractor receives the electronic document and the signature. The extractor then extracts a portion of the electronic document, and generates extraction information related to the extraction operation and updates the signature. The verifier then receives the extracted document, the signature, and the extraction information. Based on the extracted document, the signature, and the extraction information, the verifier verifies that the extracted document is the portion of the electronic document signed by the signer. A signature method satisfying the above-described process flow is defined as an extraction signature.
In order to perform the sanitization signing or the deletion signing, an electronic document is partitioned into a plurality of document segments, and the whole or part of a signing process is performed on the document segments. The size of information of a signature in the sanitization signature and the deletion signature in the related art increases substantially in proportion to the number of document segments during the signing operation. The sanitization signature and the deletion signature in the related art need to have extraction information of an amount proportional to the number of document segments to be extracted during extraction or the number of document segments to be deleted during deletion. A large amount of signature information or a large amount of extraction information is needed to extract part of a large-volume document. In other words, data efficiency of a signature is very low.
SUMI-4 is well known as a sanitization signature. SUMI-4 is disclosed in Japanese Unexamined Patent Application Publication No. 2004-364070. In this signature scheme, only one signature is used regardless of the number of document segments. In this signature scheme, however, a hash value group of document segments to be deleted during extraction is needed. The size of extraction information becomes large in proportion to the number of deleted document segments.
How the information size becomes large is discussed with reference to FIGS. 12A and 12B. During the signing operation, document information M is partitioned into document segments m1-m4. Each document segment is tagged with document segment ID information ID1-ID4. ID tagged document segments M1-M4 thus result. A signer calculates hash values h1-h4, signs the hash values h1-h4 (signature G), and sends the ID tagged document segments M1-M4 and the signature G to an extractor. During extraction, the extractor decides on an ID tagged document segment to be extracted. The extractor here may wish to extract the ID tagged document segment M2. The extractor calculates the hash values h1, h3, and h4 of the ID tagged document segments M1, M3, and M4 to be deleted, namely, not to be extracted, and discloses h1, M2, h3, and h4 and the signature G of the signer. In other words, the hash values h1, h3, and h4 are disclosed in place of the ID tagged document segments M1, M3, and M4 to be deleted. During signature verification, a verifier calculates the hash value h2 from the disclosed ID tagged partial information M2, restores the hash values h1-h4 together with the disclosed hash values h1, h3, and h4 and then verifies the hash values h1-h4 with the signature σ. Since the signature σ is a signature with which the signer signs the hash values h1-h4, the verifier can verify that the extracted ID tagged document segment M2 is part of the document M signed by the signer. If the hash value is not disclosed in place of the ID tagged document segment to be deleted, the verifier cannot verify in the extraction that the extracted ID tagged document segment M2 is part of the document M signed by the signer. For this reason, the “extraction information” as information of an amount proportional to the number of document segments to be deleted needs to be stored. If the number of ID tagged document segments to be deleted increases, the size of extraction information to be stored becomes large.
SUMI-6 is known as a deletion signature. SUMI-6 is disclosed in Japanese Unexamined Patent Application Publication No. 2006-60722. During a signing process, this signature scheme uses partial signatures responsive to document segments and an aggregate signature in which the partial signatures are aggregated. The amount of signature information increases in proportion to the number of document segments.
How the amount of signature information increases is described with reference to FIGS. 13A and 13B. In the same way as illustrated in FIGS. 12A and 12B, a signer partitions document information M into document segments m1-m4, tags the document segments m1-m4 with document segment IDs ID1-ID4 to generate ID tagged document segments M1-M4. A signer calculates hash values h1-h4, calculates partial signatures σ1-σ4 in aggregate signing to be discussed later, and aggregate the partial signatures σ1-σ4 in order to generate an aggregate signature σ. The signer finally sends to an extractor the ID tagged document segments M1-M4, the partial signatures σ1-σ4, and the aggregate signature G. During extraction, the signer decides on an ID tagged document segment to be extracted. The signer may wish to extract the ID tagged document segment M2 now. The extractor deletes the ID tagged document segment M1, M3, and M4 not to be extracted, deletes information of σ1, σ3, and σ4 from the aggregate signature G using the corresponding partial signatures σ1, σ3, and σ4, and updates the aggregate signature to be σ′. The extractor finally discloses the extracted ID tagged document segment M2, the partial signature σ2, and the updated aggregate signature σ′. During signature verification, a verifier performs a verification operation with the ID tagged document segment M2 and the updated aggregated signature σ′. The signature σ′ results from deleting, from the aggregate signature G of the signer, information of the partial signatures of the ID tagged document segments M1, M3, and M4 deleted by the extractor. For this reason, the verifier can verify that the extracted ID tagged document segment M2 is part of the document M signed by the signer.
In this signature scheme, partial signature information is added in the signing operation. Signature information in an amount proportional to the number of document segments to be signed is stored. In other words, the larger the number of ID tagged document segments to be signed, the larger the size of signature information to be stored.
In the sanitization signature based extraction, the number of signatures is one (small amount of data) in the signing operation, but extraction information for the number of document segments to be deleted is to be stored in addition to the signature at the extraction (large amount of data). In the deletion signature based extraction, an extraction document, an partial signature therefore, and an updated aggregate signature are sufficient (small amount of data) at the extraction. During signing, partial signatures for the document segments in addition to the “aggregate signature” are stored (large amount of data).
On the other hand, a digital signature application technique called “aggregate signature” is also available. If one signer or a plurality of signers signs one electronic document or a plurality of electronic documents in the circulation of the electronic documents, the signatures may be aggregated in order to reduce an amount of signature data.
The representative characteristics of the aggregate signature are described. A plurality of persons may sign a plurality of documents. Signature data of the number of units equal to the number of documents is used in ordinary digital signature as illustrated in FIG. 14. In contrast, if the aggregate signature is used, the signatures of the documents are aggregated into a single signature as illustrated in FIG. 15. In other words, the amount of signature data is reduced.
A sequential aggregate signature based on RSA signature is currently known. The sequential aggregate signature is disclosed in the paper entitled “Sequential Aggregate Signatures from Trapdoor Permutations,” contributed by A. Lysyanskaya, et. al., EUROCRYPT 2004, LNCS 3027, pp. 74-90, 2004. Also known is a general aggregate signature. The general aggregate signature is based on pairing as one of the elliptic curve cryptography techniques, described in the paper entitled “Aggregate and Verifiability Encrypted Signature from Bilinear Maps,” contributed by D. Bone, et. al., EUROCRYPT 2003, LNCS 2656, pp. 416-432, 2003. The general aggregate signature is used in the above-described deletion signature.
The technique called RSA accumulator is disclosed in the paper entitled “One-way accumulators: A Decentralized Alternative to Digital Signatures,” contributed by J. Benaloh, and M. de Mare, EUROCRYPT '93, LNCS 765, pp. 274-285, Springer-Verlag, 1994. The RSA accumulator is one type of hash function based on the RSA cryptography, and has an aggregation function. As the RSA cryptography, the RSA accumulator uses N which is a product of two prime numbers p and q. The RSA accumulator also uses element g mutually prime to N, and the order of the element g, φ=LCM(p−1)(q−1). The RSA accumulator has a pseudo-commutative property based on the integrity of the RSA assumption. If function f:X*Y→X satisfies the following features under the condition of all xεX and all y1 and y2εY, the function is considered as having the pseudo-commutative property:f(f(x,y1),y2)=f(f(x,y2),y1)
If the function f is repeatedly applied, the order of y is modifiable, i.e., commutative. The RSA accumulator in the above-described document embodies the function f as fN(x,y)=*h(y) mod N. Here, H represents a one-way hash function, such as SHA 1.
In the RSA accumulator, the following equation holds:gH(y1)*H(y2)mod N=(gH(y1)mod N)H(y2)mod N =(gH(y2)mod N)H(y1)mod N 
In other words, the hash values are aggregated in random order. Since the RSA accumulator has a one-way feature, it is difficult to calculate x from (gH(y)mod N) and H(y), N (so-called the RSA assumption).
Each of the above-described sanitization signature techniques, the deletion signature technique, and sanitization and deletion signature technique can set a variety of states related to sanitization and deletion on each document segment. The states set to each document segment are described below. The related technique is disclosed in the paper entitled “On sanitizable and deletion signature schemes,” M. Sano, T. Izu, N. Kunihiro, K. Ohta, and M. Takenaka, Symposium on Cryptography and Information Security, pp. 156, January 2007.
FIG. 16 illustrates document segment states and state transitions. Referring to FIG. 16, a chart 3400 denotes a variety of states settable on each document segment. More specifically, FIG. 16 illustrates six states responsive to combinations of a prohibited attribute, an allowed attribute, and a sanitized or deleted attribute related to the sanitization and the deletion.
The six states includes a sanitization allowed and deletion allowed (SADA) state, a sanitization prohibited and deletion prohibited (SPDP) state, a sanitization allowed and deletion prohibited (SADP) state, a sanitized and deletion allowed (SDA) state, a sanitized and deletion prohibited (SDP) state, and a deleted (D) state.
Nine state transitions Ta-Ti are also illustrated to represent state transitions between the states. For example, the state transition Ta represents a transition from the SADA state where the document segment is sanitization allowed and deletion allowed to the SPDP state where the document segment is sanitization prohibited and deletion prohibited.
The six states and the nine state transitions are not set in each document segment as a property but are physically set through a data storage method. In this way, the document segment may be set in a variety of states depending on whether the document segment is to be disclosed, not to be disclosed, or to be revised. An information leak of a electronic document due to an error in the setting of the property is thus controlled.